package org.example.myleet.p591;

import java.util.Deque;
import java.util.LinkedList;

public class Solution {

    //状态机的几种状态：开始标签检查、结束标签检查、内容检查、CDATA检查
    private static final int DEFAULT_STATE = 0;
    private static final int START_TAG_STATE = 1;
    private static final int END_TAG_STATE = 2;
    private static final int CONTENT_STATE = 3;
    private static final int CDATA_STATE = 4;

    public boolean isValid(String code) {
        Deque<String> tagStack = new LinkedList<>();
        char[] codeChars = code.toCharArray();
        if (codeChars.length < 1) {
            return false;
        }
        //因为整个文档需要包含在标签中，因此第一个字符必须为'<'，处于开始标签状态
        if (codeChars[0] != '<') {
            return false;
        }
        int i = 1, n = codeChars.length, state = START_TAG_STATE;
        char c;
        StringBuilder sb = new StringBuilder();
        while (i < n) {
            c = codeChars[i++];
            switch (state) {
                case START_TAG_STATE: {
                    if (c == '>') {
                        //找到一对'<>'，检查长度，然后入栈，待寻找结束标签，状态变成内容检查状态
                        if (sb.length() < 1 || sb.length() > 9) {
                            return false;
                        }
                        tagStack.push(sb.toString());
                        sb = new StringBuilder();
                        state = CONTENT_STATE;
                    } else if (c == '/') {
                        //找到'</'，则切换到结束标签检查状态
                        state = END_TAG_STATE;
                    } else if (c == '!') {
                        //找到'<!'，尝试进入CDATA检查状态，'<![CDATA['，只要有一个不匹配都不能进入CDATA状态，而且不会回头
                        c = codeChars[i++];
                        if (c == '[') {
                            c = codeChars[i++];
                            if (c == 'C') {
                                c = codeChars[i++];
                                if (c == 'D') {
                                    c = codeChars[i++];
                                    if (c == 'A') {
                                        c = codeChars[i++];
                                        if (c == 'T') {
                                            c = codeChars[i++];
                                            if (c == 'A') {
                                                c = codeChars[i++];
                                                if (c == '[') {
                                                    state = CDATA_STATE;
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    } else if (!Character.isUpperCase(c)) {
                        //题目要求开始标签要大写
                        return false;
                    } else {
                        //继续拼接开始标签名称
                        sb.append(c);
                    }
                    break;
                }
                case END_TAG_STATE: {
                    if (c == '>') {
                        //找到一对'</>'，要求栈顶有对应的开始标签，状态切换到内容检查状态
                        if (tagStack.isEmpty()) {
                            return false;
                        }
                        String startTag = tagStack.poll();
                        if (!startTag.equals(sb.toString())) {
                            return false;
                        }
                        sb = new StringBuilder();
                        state = CONTENT_STATE;
                        if (tagStack.isEmpty() && i < n) {
                            //这里需要注意一下如果栈空了代表已经检查完最外层标签，但是如果还没结束说明根节点外还有内容，不合法
                            return false;
                        }
                    } else if (!Character.isUpperCase(c)) {
                        //题目要求开始和结束标签要大写
                        return false;
                    } else {
                        //继续拼接结束标签名称
                        sb.append(c);
                    }
                    break;
                }
                case CONTENT_STATE: {
                    if (c == '<') {
                        //存在'<'，切换到开始标签检查状态
                        state = START_TAG_STATE;
                    }
                    break;
                }
                case CDATA_STATE: {
                    if (tagStack.isEmpty()) {
                        //这里要注意，如果CDATA不在任何标签范围内，也不合法
                        return false;
                    }
                    //CDATA的结束必须包含']]>'，但是当'>'找不到时，考虑到']]'这种连续两个相同字符串可能会多次出现在']]]>'里面
                    //因此i需要往前回退2个位置
                    if (c == ']') {
                        c = codeChars[i++];
                        if (c == ']') {
                            c = codeChars[i++];
                            if (c == '>') {
                                state = CONTENT_STATE;
                            } else {
                                i -= 2;
                            }
                        }
                    }
                    break;
                }
            }
        }
        //文档内容已遍历完成，最终状态需要是内容检查状态并且已经退出所有的标签
        return state == CONTENT_STATE && tagStack.isEmpty();
    }
}
